#ifndef PW_PBL_BITSET_HPP
#define PW_PBL_BITSET_HPP

#include "IntFor.hpp"
#include <span>
#include <bit>

namespace pw_pbl
{
	namespace _bitset
	{
		inline constexpr auto EBestBitcnt = Math::BitCntOf<size_t>;

		template <size_t N>
		using TCell = UIntFor::BitCnt<N % EBestBitcnt ? N % EBestBitcnt : EBestBitcnt>;

		template <std::unsigned_integral TCell>
		constexpr void init(std::span<TCell> data, std::span<const bool> ini) noexcept
		{
			constexpr auto ECellBits = Math::BitCntOf<TCell>;
			for (size_t i = 0, sz = data.size(); i < sz; i++)
				for (size_t j = 0; j < ECellBits; j++)
				{
					auto id = i * ECellBits + j;
					if (id >= ini.size())
						return;
					if (auto v = ini[id]; v)
						data[i] |= TCell(v) << j;
				}
		}

		template <size_t EDummyBits, std::unsigned_integral TCell> requires(EDummyBits < Math::BitCntOf<TCell>)
		constexpr bool matchAllThen(std::span<const TCell> data, TCell V, bool out) noexcept
		{
			auto ECellCnt = data.size();
			for (size_t i = 0, cnt = EDummyBits ? ECellCnt - 1 : ECellCnt; i < cnt; i++)
				if (data[i] != V)
					return !out;
			if constexpr (EDummyBits)
				return TCell(data[ECellCnt - 1] << EDummyBits) == TCell(V << EDummyBits) ? out : !out;
			else
				return out;
		}

		template <size_t EDummyBits, std::unsigned_integral TCell> requires(EDummyBits < Math::BitCntOf<TCell>)
		constexpr size_t count(std::span<const TCell> data) noexcept
		{
			size_t out = 0;
			auto ECellCnt = data.size();
			for (size_t i = 0, cnt = EDummyBits ? ECellCnt - 1 : ECellCnt; i < cnt; i++)
				out += std::popcount(data[i]);
			if constexpr (EDummyBits)
				return out += std::popcount(TCell(data[ECellCnt - 1] << EDummyBits)), out;
			else
				return out;
		}
	}; // namespace _bitset

	template <size_t N, typename CELL = _bitset::TCell<N>>
	struct Bitset
	{
		using TCell = CELL;
		static constexpr auto ECellBits = Math::BitCntOf<TCell>;
		static constexpr auto EPosRemMask = ECellBits - 1;
		static constexpr auto ECellCnt = Math::CeilDivide(N, ECellBits);
		static constexpr auto EDummyBits = ECellCnt * ECellBits - N;

		TCell data[ECellCnt];

		constexpr Bitset() noexcept = default;
		constexpr Bitset(std::span<const bool> ini) noexcept : data{} { _bitset::init(data, ini.subspan(0, std::min(N, ini.size()))); }
		template <std::convertible_to<bool>... T> requires(sizeof...(T) <= N)
		constexpr Bitset(T &&...v) noexcept : data{} { _bitset::init<TCell>(data, std::initializer_list<bool>{bool(v)...}); };

		// clang-format off
		static constexpr size_t cell_index(size_t pos) { if constexpr (ECellCnt == 1) return 0; else return pos >> Math::Log2<ECellBits>; }
		static constexpr size_t bit_offset(size_t pos) { if constexpr (ECellCnt == 1) return pos; else return pos & EPosRemMask; }
		// clang-format on

		constexpr bool test(size_t pos) const noexcept { return data[cell_index(pos)] >> bit_offset(pos) & 1; }
		constexpr bool operator[](size_t pos) const noexcept { return test(pos); }

		constexpr bool all() const noexcept { return _bitset::matchAllThen<EDummyBits, TCell>(data, std::numeric_limits<TCell>::max(), true); }
		constexpr bool any() const noexcept { return _bitset::matchAllThen<EDummyBits, TCell>(data, 0, false); }
		constexpr bool none() const noexcept { return _bitset::matchAllThen<EDummyBits, TCell>(data, 0, true); }
		constexpr size_t count() const noexcept { return _bitset::count<EDummyBits, TCell>(data); }
		static constexpr size_t size() noexcept { return N; }
		constexpr Bitset &set(size_t pos, bool value) noexcept { return value ? set(pos) : reset(pos); }
		constexpr Bitset &set(size_t pos) noexcept { return (data[cell_index(pos)] |= TCell(1) << bit_offset(pos)), *this; }
		constexpr Bitset &reset(size_t pos) noexcept { return (data[cell_index(pos)] &= ~(TCell(1) << bit_offset(pos))), *this; }
		constexpr Bitset &flip(size_t pos) noexcept { return (data[cell_index(pos)] ^= TCell(1) << bit_offset(pos)), *this; }
		constexpr Bitset &set() noexcept { return std::fill_n(data, ECellCnt, std::numeric_limits<TCell>::max()), *this; }
		constexpr Bitset &reset() noexcept { return std::fill_n(data, ECellCnt, 0), *this; }
	};

	template <size_t N, typename CELL> requires(N * sizeof(bool) <= sizeof(CELL))
	struct Bitset<N, CELL>
	{
		using TCell = CELL;
		static constexpr TCell EAllSeted = [] {
			TCell value = 0;
			for (auto i = 0; i < N; i++)
				value = value << Math::BitCntOf<bool> | true;
			return value;
		};
		union
		{
			TCell all;
			bool bits[N];
		} data;

		constexpr Bitset() noexcept = default;
		constexpr Bitset(std::span<const bool> ini) noexcept : data{}
		{
			for (auto i = 0; i < N; i++)
				data.bits[i] = ini[i];
		}
		template <std::convertible_to<bool>... T> requires(sizeof...(T) <= N)
		constexpr Bitset(T &&...v) noexcept : data{.bits = {v...}} {};

		constexpr bool test(size_t pos) const noexcept { return data.bits[pos]; }
		constexpr bool operator[](size_t pos) const noexcept { return test(pos); }

		constexpr bool all() const noexcept { return data.all == EAllSeted; }
		constexpr bool any() const noexcept { return data.all != 0; }
		constexpr bool none() const noexcept { return data.all == 0; }
		constexpr size_t count() const noexcept { return std::popcount(data.all); }
		static constexpr size_t size() noexcept { return N; }
		constexpr Bitset &set(size_t pos, bool value) noexcept { return (data.bits[pos] = value), *this; }
		constexpr Bitset &set(size_t pos) noexcept { return (data.bits[pos] = true), *this; }
		constexpr Bitset &reset(size_t pos) noexcept { return (data.bits[pos] = false), *this; }
		constexpr Bitset &flip(size_t pos) noexcept { return (data.bits[pos] ^= true), *this; }
		constexpr Bitset &set() noexcept { return (data.all = EAllSeted), *this; }
		constexpr Bitset &reset() noexcept { return (data.all = 0), *this; }
	};

	template <std::convertible_to<bool>... T>
	Bitset(T &&...) -> Bitset<sizeof...(T)>;
} // namespace pw_pbl

#endif // PW_PBL_BITSET_HPP
